package leetcode;

import scala.swing.model.Matrix;

import java.util.*;

/**
 * Created by liuwei on 2018/1/25.
 */
public class Solution {



    public int removeElement(int[] nums, int val) {
        int i = 0;
        int n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                // reduce array size by one
                n--;
            } else {
                i++;
            }
        }
        return n;
    }


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int sum ;
        for(int i=0;i<nums.length;i++){
            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                if(i > 0 && nums[i] == nums[i-1]) right = 0;
                else {
                    sum = nums[i] + nums[left] + nums[right];
                    if(sum ==0){
                        List<Integer> l = new ArrayList<>();
                        l.add(nums[i]);
                        l.add(nums[left]);
                        l.add(nums[right]);
                        list.add(l);
                        left ++;
                        right --;
                        while(left < right && nums[left] == nums[left-1]){
                            left ++;
                        }
                        while(left < right && nums[right] == nums[right+1]){
                            right --;
                        }
                    }else  if (sum < 0) left ++;
                    else right --;
                }
            }
        }


        return list;

    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        HashSet set = new HashSet();
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            for(int j = 1;j< nums.length;j++){
                if(nums[i] == nums[j]) continue;
                int l = 2;
                int r = nums.length;
                int sum = nums[i] +nums[j] +nums[l] +nums[r];
                if(sum == target){
                    List<Integer> o = new ArrayList<Integer>();
                    o.add(nums[i]);
                    o.add(nums[j]);
                    o.add(nums[l]);
                    o.add(nums[r]);
                    list.add(o);
                    l ++;
                    r --;
                }else if(sum > target){
                    r--;
                }else{
                    l++;
                }
            }
        }
        return list;

    }


    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>(9);
        for(int i=1;i<=n;i++)
        {
            nums.add(i);
        }
        int[] arr= new int[n];
        arr[0] =1;
        StringBuilder sb = new StringBuilder(9);
        for(int i=1;i<=n-1;i++){
            arr[i] = i*arr[i-1];
        }
        k--;
       for(int i=n ;i>0;i--){
            int j = k/arr[i-1];
            k %= arr[i-1];
           sb.append(nums.get(j));
           nums.remove(nums.get(j));
       }
        return sb.toString();
    }


    public String simplifyPath(String path) {
        while(path.contains("//")){
            path = path.replaceAll("//","/");
        }

        String[] strArr = path.split("/");
        List<String> list = Arrays.asList(strArr);
        List<String> strList = new ArrayList<>(list);

        while(strList.contains(".")||strList.contains("..")){
            for(int i=0;i<strList.size();i++){
                if(".".equals(strList.get(i))){
                     strList.remove(i);
                     break;
                }else  if(strList.get(i).equals("..") ){
                    strList.remove(i);
                    if(i!=0)  strList.remove(i-1);
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(String str:strList){
            if( !"".equals(str) ){
                sb.append("/");
                sb.append(str);
            }
        }
        if(sb.length()==0) return "/";
        return sb.toString();

    }


    public String simplifyPath2(String path) {
        Stack<String> s = new Stack<>();
        String[] p = path.split("/");
        for (String t : p) {
            if (!s.isEmpty() && t.equals("..")) {
                s.pop();
            } else if (!t.equals(".") && !t.equals("") && !t.equals("..")) {
                s.push(t);
            }
        }
        List<String> list = new ArrayList(s);
        return "/" + String.join("/", list);
    }

    public int minDistance(String word1, String word2) {
        int m = word1.length()+1;
        int n = word2.length()+1;
        char[] char1 = word1.toCharArray();


        char[] char2 = word2.toCharArray();
        int[][] arr = new int[m][n];
        for(int i=0;i<m;i++){
            arr[i][0] = i;
        }
        for(int i=0;i<n;i++){
            arr[0][i] = i;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(char1[i-1] == char2[j-1]){
                    arr[i][j]=arr[i-1][j-1];
                }else{
                    arr[i][j]= Math.min(arr[i-1][j]+1,Math.min(arr[i-1][j-1]+1,arr[i][j-1]+1));
                }
            }
        }
        return arr[m-1][n-1];
    }
    public  static void  main(String [] args) {
        int[] arr =new int[]{3,2,2,3};
        System.out.println(new Solution().minDistance("a","a"));
//        System.out.println(arr.length);

    }


}
